package leetcode_1701_1800;

public class LeeCode_1712 {
    public static void main(String[] args) {
//        System.out.println(waysToSplit(new int[]{1, 1, 1}));
//        System.out.println(waysToSplit(new int[]{1,2,2,2,5,0}));
//        System.out.println(waysToSplit(new int[]{3,2,1}));
        int[] arr = new int[5];
        System.out.println(waysToSplit(arr));
    }
    private static int waysToSplit(int[] nums) {
        int n = nums.length;
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        long ans = 0, mod = (long) (1e9 + 7);
        for (int i = 1; i < n + 1; i++) {
            if ((sums[n] + 2) / 3 < sums[i]){
                break;
            }
            int mr = smaller(sums, i), ml = bigger(sums, i);
            if (ml == -1 || mr == -1){
                continue;
            }
            ans += mr - ml + 1;
            ans %= mod;
        }
        return (int) ans;
    }
    private static int bigger(int[] sums, int start){
        int l = start + 1, r = sums.length - 1;
        if (l > r)
            return -1;
        while (l < r){
            int m = (l + r) / 2;
            if (sums[m] >= sums[start] * 2){
                r = m;
            }else {
                l = m + 1;
            }
        }
        if (sums[l] < sums[start] * 2)
            return -1;
        return l;
    }
    private static int smaller(int[] sums, int start){
        int n = sums.length;
        int l = start + 1, r = n - 2;
        if (l > r)
            return -1;
        while (l < r){
            int m = (l + r + 1) / 2;
            if (sums[n - 1] - sums[m] >= sums[m] - sums[start]){
                l = m;
            }else {
                r = m - 1;
            }
        }
        if (sums[n - 1] - sums[l] < sums[l] - sums[start]){
            return -1;
        }
        return l;
    }
}
